# 69/100 栈-有效括号
# leetcode第20题: https://leetcode.cn/problems/valid-parentheses/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/23
from leetcode import test


def isValid(s: str) -> bool:
    n = len(s)
    begin = {'(', '[', '{'}
    stack = []
    for i in range(n):
        if s[i] in begin:
            stack.append(s[i])
        elif s[i] == ')':
            if len(stack) == 0 or stack.pop() != '(':
                return False
        elif s[i] == ']':
            if len(stack) == 0 or stack.pop() != '[':
                return False
        elif s[i] == '}':
            if len(stack) == 0 or stack.pop() != '{':
                return False
    return len(stack) == 0


def isValid_opt(s: str) -> bool:
    n = len(s)
    if n % 2 == 1:
        return False

    pairs, stack = {
        ")": "(",
        "]": "[",
        "}": "{",
    }, []
    for ch in s:
        if ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
        else:
            stack.append(ch)

    return not stack


if __name__ == '__main__':
    inp = [{"s": "()"}, {"s": "()[]{}"}, {"s": "(]"}, {"s": "("}, {"s": ")"}, {"s": "([])"}, {"s": "([]{})"}, ]
    out = [True, True, False, False, False, True, True]
    test.test_function(isValid, inp, out, times=10000)
    test.test_function(isValid_opt, inp, out, times=10000)
